﻿#include <iostream>
using namespace std;

int commFactor(int m, int n){
	int i, factor = 1;
	for(i = 2; i <= m && i <= n; i++){
		while(m % i == 0 && n % i ==0){
			factor = factor * i;
			m = m / i;
			n = n / i;
		}
	}
	return factor;
}

void egyptFraction(int a, int b){
	int e, r;
	cout << a << "/" << b << " = ";		//输出真分数
	do{
		e = b / a + 1;					//求真分数A/B包含的最大埃及分数
		cout << "1/" << e << " + ";		//输出1/E
		a = a * e - b;					//以下两条语句计算A/B-1/E
		b = b * e;
		r = commFactor(b, a);			//函数调用，求A和B的最大公约数
		if(r > 1){						//最大公约数大于1，即A/B可以化简
			a = a / r;					//将A/B化简
			b = b / r;
		} 
	} while(a > 1);						//当A/B不是埃及分数时执行循环
	cout << "1/" << b << endl;			//输出最后一个埃及分数1/B
	
	return;
}

int main(){
	int a, b;
	cout << "输入真分数 A/B：";
	cin >> a;
	cin >> b;
	egyptFraction(a, b);
	
	system("pause");
	return 0;
}